﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace SuffixTrie
{
    /// <summary>
    /// 后缀树节点
    /// </summary>
    public class SuffixNode
    {
        /// <summary>
        /// 节点文本
        /// </summary>
        private string text;

        /// <summary>
        /// 以该节点结尾的单词频度
        /// 单词尾节点则频度+1；为0时表示前缀子串
        /// </summary>
        private int freq = 0;

        /// <summary>
        /// 子节点
        /// </summary>
        private List<SuffixNode> children = new List<SuffixNode>();

        /// <summary>
        /// 文本
        /// </summary>
        public string Text
        {
            get
            {
                return text;
            }
            set
            {
                text = value;
            }
        }

        /// <summary>
        /// 频度
        /// </summary>
        public int Frequentness
        {
            get
            {
                return freq;
            }
            set
            {
                if (value >= 0)
                    freq = value;
                else
                    freq = 0;
            }
        }

        /// <summary>
        /// 子节点
        /// </summary>
        public List<SuffixNode> Children
        {
            get
            {
                return children;
            }
            set
            {
                children.Clear();
                children.AddRange(value);
            }
        }

        /// <summary>
        /// 增加子节点
        /// </summary>
        /// <param name="node">子节点</param>
        public void AddChild(SuffixNode node)
        {
            if (node == null)
                return;

            SuffixNode child = children.Find(delegate(SuffixNode nd) { return nd.text == node.text; });
            if (child == null)
                children.Add(node);
            else
                child.freq += node.freq;
        }
    }

    /// <summary>
    /// 后缀树
    /// </summary>
    class SuffixTree
    {
        /// <summary>
        /// 树根
        /// </summary>
        private SuffixNode root = new SuffixNode();

        /// <summary>
        /// 根节点
        /// </summary>
        public SuffixNode Root
        {
            get
            {
                return root;
            }
        }

        /// <summary>
        /// 增加节点
        /// </summary>
        /// <param name="text"></param>
        public void AddNode(string text)
        {
            if (String.IsNullOrWhiteSpace(text))
                return;

            text = text.Trim();

            bool isSuffix = false;
            // 依次加入后缀节点
            for (int i = 0; i < text.Length; ++i)
            {
                if (i > 0)
                    isSuffix = true;

                string s = text.Substring(i);
                AddTreeNode(root, s, isSuffix);
            }
        }

        /// <summary>
        /// 批量增加节点
        /// </summary>
        /// <param name="texts"></param>
        public void AddNodes(string[] texts)
        {
            foreach (string s in texts)
                AddNode(s);
        }

        /// <summary>
        /// 增加树节点
        /// </summary>
        /// <param name="parent">父节点</param>
        /// <param name="text">文本</param>
        /// <param name="isSuffix">是否后缀</param>
        private void AddTreeNode(SuffixNode parent, string text, bool isSuffix)
        {
            Debug.Assert(parent != null);
            if (parent == null)
                return;

            // 前缀字符位置
            int fixpos = 0;

            // 相同字符个数
            int fixnum = 0;

            // 前缀节点
            SuffixNode pre = SearchPrefixNode(text, ref fixpos, out fixnum);

            if (pre == null)
            {
                // 不存在前缀节点，新增节点
                SuffixNode newnode = new SuffixNode();
                newnode.Text = text;
                newnode.Frequentness = isSuffix ? 0 : 1;    // 单词后缀则频度为0

                parent.AddChild(newnode);
            }
            else
            {
                Debug.Assert(fixnum > 0);

                // 前缀节点部分字符相同，则炸开前缀节点
                if (fixnum < pre.Text.Length)
                {
                    ExplodeNode(ref pre, fixnum);
                }

                // 找到相同的前缀个数
                int pos = fixpos + fixnum;

                // 整个文本都在前缀节点中
                if (pos >= text.Length)
                {
                    if (!isSuffix)
                        pre.Frequentness++; // 频度+1
                }
                else
                {
                    // 仅有部分文本在前缀节点中
                    SuffixNode child = new SuffixNode();
                    child.Text = text.Substring(pos);
                    child.Frequentness = isSuffix ? 0 : 1;  // 单词后缀则频度为0

                    pre.Children.Add(child);
                }
            }
        }

        /// <summary>
        /// 查找前缀节点
        /// 查找树中与文本有相同前缀的节点，并取得最后一个匹配节点在文本中的字符位置及相同的字符个数
        /// </summary>
        /// <param name="text">文本</param>
        /// <param name="fixpos">前缀节点字符在文本中的位置</param>
        /// <param name="fixnum">与前缀节点相同的字符个数</param>
        /// <returns>前缀节点</returns>
        private SuffixNode SearchPrefixNode(string text, ref int fixpos, out int fixnum)
        {
            fixpos = 0;
            fixnum = 0;

            foreach (SuffixNode node in root.Children)
            {
                SuffixNode pre = SearchPrefixNode(node, text, ref fixpos, out fixnum);
                if (pre != null)
                    return pre;
            }

            return null;
        }

        /// <summary>
        /// 查找前缀节点
        /// </summary>
        /// <param name="node">查找节点</param>
        /// <param name="text">文本</param>
        /// <param name="fixpos">前缀节点字符在文本中的位置</param>
        /// <param name="fixnum">与前缀节点相同的字符个数</param>
        /// <returns>前缀节点</returns>
        private SuffixNode SearchPrefixNode(SuffixNode node, string text, ref int fixpos, out int fixnum)
        {
            fixnum = 0;

            if (node == root)
                return null;

            // 相同前缀的字符个数
            int num = GetSamePrefixNumber(node.Text, text);

            // 没有相同前缀
            if (num <= 0)
                return null;

            // 节点仅部分前缀相同
            if (num < node.Text.Length)
            {
                fixnum = num;
                return node;
            }

            // 节点全部为前缀，继续查找子节点
            if (num < text.Length)
            {
                string sub = text.Substring(num);

                foreach (SuffixNode child in node.Children)
                {
                    int num2 = 0;
                    SuffixNode pre = SearchPrefixNode(child, sub, ref fixpos, out num2);
                    if (pre != null)
                    {
                        // 子节点为前缀，则修改前缀位置及个数
                        fixpos = fixpos + fixnum + num;
                        fixnum = num2;
                        return pre;
                    }
                }
            }

            // 子节点都不是前缀
            fixnum = num;
            return node;
        }

        /// <summary>
        /// 获取相同前缀的字符个数
        /// </summary>
        /// <param name="s1">字符串1</param>
        /// <param name="s2">字符串2</param>
        /// <returns>相同前缀字符个数</returns>
        private int GetSamePrefixNumber(string s1, string s2)
        {
            if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
                return 0;

            int n = 0;

            do
            {
                if (s1[n] == s2[n])
                    n++;
                else
                    break;
            } while (n < s1.Length && n < s2.Length);

            return n;
        }

        /// <summary>
        /// 炸开节点
        /// </summary>
        /// <param name="node">节点</param>
        /// <param name="pos">炸开位置</param>
        private void ExplodeNode(ref SuffixNode node, int pos)
        {
            if (node == root)
                return;

            if (pos == 0 || pos >= node.Text.Length)
                return;

            // 炸开后的子节点
            SuffixNode child = new SuffixNode();
            child.Text = node.Text.Substring(pos);
            child.Frequentness = node.Frequentness;
            child.Children = node.Children;

            // 炸开后的父节点
            node.Text = node.Text.Substring(0, pos);
            node.Frequentness = 0;
            node.Children.Clear();
            node.Children.Add(child);
        }

        /// <summary>
        /// 查找文本是否存在
        /// </summary>
        /// <param name="text">文本</param>
        /// <returns>返回词组频度（个数）</returns>
        public int SearchText(string text)
        {
            int fixpos = 0;
            int fixnum = 0;
            SuffixNode node = SearchPrefixNode(text, ref fixpos, out fixnum);
            if (node == null || node.Frequentness <= 0)
                return 0;

            if (fixnum < node.Text.Length)
                return 0;

            if (fixpos + fixnum == text.Length)
                return node.Frequentness;

            return 0;
        }

        /// <summary>
        /// 搜索前缀字符串
        /// </summary>
        /// <param name="pretext"></param>
        /// <returns></returns>
        public string[] SearchPrefixText(string pretext)
        {
            List<string> ret = new List<string>();

            int fixpos = 0;
            int fixnum = 0;
            SuffixNode node = SearchPrefixNode(pretext, ref fixpos, out fixnum);

            if (node != null)
            {
                if (fixpos > 0)
                    GetAllText(node, pretext.Substring(0, fixpos + fixnum - 1), ref ret);
                else
                    GetAllText(node, "", ref ret);
            }

            return ret.ToArray();
        }

        /// <summary>
        /// 获得所有词组
        /// </summary>
        /// <param name="node">节点</param>
        /// <param name="pretext">节点前缀文本</param>
        /// <param name="ret">返回词组</param>
        private void GetAllText(SuffixNode node, string pretext, ref List<string> ret)
        {
            string s = pretext + node.Text;
            if (node.Frequentness > 0)
                ret.Add(s);

            foreach (SuffixNode nd in node.Children)
                GetAllText(nd, s, ref ret);
        }
    }
}